package com.chengzhi.structure;

/**
 * @description: 线段树
 * @author: ruanchengzhi
 * @create: 2020-03-13 10:39
 **/
public class SegmentTree<T> {

    private T[] data;

    private T[] tree;

    private Merge<T> merge;

    public SegmentTree(T[] arr, Merge<T> merge) {
        this.merge = merge;
        data = (T[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }
        tree = (T[]) new Object[arr.length * 4];

        buildSegmentTree(0, 0, data.length - 1);
    }

    /**
     * 构建树 从left到right
     *
     * @param index 当前值
     * @param left
     * @param right
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/3/13
     */
    private void buildSegmentTree(int index, int left, int right) {
        if (left == right) {
            tree[index] = data[left];
            return;
        }
        int leftChildIndex = leftChlidIndex(index);
        int rightChildIndex = rihgtChlidIndex(index);
        int mid = left + (right - left) / 2;
        buildSegmentTree(leftChildIndex, left, mid);
        buildSegmentTree(rightChildIndex, mid + 1, right);
        tree[index] = merge.merge(tree[leftChildIndex], tree[rightChildIndex]);
    }


    /**
     * 范围查找
     *
     * @param leftQuery  左边界
     * @param rightQuery 右边界
     * @return: T
     * @author: ruanchengzhi
     * @date: 2020/3/14
     */
    public T query(int leftQuery, int rightQuery) {
        if (leftQuery > rightQuery || leftQuery > tree.length || rightQuery > tree.length) {
            throw new IllegalArgumentException("index not regex");
        }
        return query(0, 0, data.length - 1, leftQuery, rightQuery);
    }

    /**
     * 递归查询
     *
     * @param index      索引
     * @param left       左
     * @param right      右
     * @param leftQuery  左边界
     * @param rightQuery 右边界
     * @return: T
     * @author: ruanchengzhi
     * @date: 2020/3/14
     */
    private T query(int index, int left, int right, int leftQuery, int rightQuery) {
        if (left == right) {
            return tree[index];
        }
        int mid = left + (right - left) / 2;
        int leftChildIndex = leftChlidIndex(index);
        int rightChildIndex = rihgtChlidIndex(index);
        if (rightQuery <= mid) {
            return query(leftChildIndex, left, mid, leftQuery, rightQuery);
        }
        if (leftQuery >= mid + 1) {
            return query(rightChildIndex, mid + 1, right, leftQuery, rightQuery);
        }
        return merge.merge(query(leftChildIndex, left, mid, leftQuery, mid), query(rightChildIndex, mid + 1, right, mid + 1, rightQuery));
    }

    public void set(int index, T t) {
        if (index < 0 || index > data.length) {
            throw new IllegalArgumentException("index not regex");
        }
        data[index] = t;
        set(0, 0, data.length - 1, index, t);
    }

    private void set(int treeIndex, int left, int right, int index, T t) {
        if (left == right) {
            tree[treeIndex] = t;
            return;
        }
        int mid = left + (right - left) / 2;
        int leftChildIndex = leftChlidIndex(treeIndex);
        int rightChildIndex = rihgtChlidIndex(treeIndex);
        if (index >= mid + 1) {
            set(rightChildIndex, mid + 1, right, index, t);
        } else {
            set(leftChildIndex, left, mid, index, t);
        }
        tree[treeIndex] = merge.merge(tree[leftChildIndex], tree[rightChildIndex]);
    }


    public int getSize() {
        return data.length;
    }

    /**
     * 左孩子索引
     *
     * @param index
     * @return: int
     * @author: ruanchengzhi
     * @date: 2020/3/13
     */
    private int leftChlidIndex(int index) {
        return index * 2 + 1;
    }

    /**
     * 右孩子索引
     *
     * @param index
     * @return: int
     * @author: ruanchengzhi
     * @date: 2020/3/13
     */
    private int rihgtChlidIndex(int index) {
        return index * 2 + 2;
    }
}

